
module type GEN = 
sig

  module O : Ordered.T 

  exception Empty

  (* Nodes *)
  type 'a node 
  val value : 'a node -> 'a
  val priority : 'a node -> O.t
  val node_to_string : ('a -> string) -> 'a node -> string

  (* DEBUG *)
  val set_prio : 'a node -> O.t -> unit

  (* Heaps *)
  type 'a t
  val create : unit -> 'a t
  val build : 'a node array -> 'a t
  val insert : 'a t -> O.t * 'a -> 'a node
  val heapsort : 'a node array -> unit
  val size : 'a t -> int
  val to_string : ('a -> string) -> 'a t -> string
  val empty : 'a t -> bool

  val grow_factor : int ref
  val shrink_factor : int ref

end

module type IMP_MAX = 
sig
  include GEN
  val maximum : 'a t -> O.t * 'a
  val extract_max : 'a t -> O.t * 'a (* raises Empty *)
  val increase_key : 'a t -> 'a node -> O.t -> unit
end

module type IMP_MIN = 
sig
  include GEN
  val minimum : 'a t -> O.t * 'a
  val extract_min : 'a t -> O.t * 'a (* raises Empty *)
  val decrease_key : 'a t -> 'a node -> O.t -> unit
end

(* -------------------------------------------------------------------------- *)
(*  Default implementation                                                    *)
(* -------------------------------------------------------------------------- *)

module MaxHeap(O' : Ordered.BASE) : IMP_MAX with module O = Ordered.S(O') 

module MinHeap(O' : Ordered.BASE) : IMP_MIN with module O = Ordered.S(O') 

module MaxInt : IMP_MAX with module O = Ordered.Int
module MinInt : IMP_MIN with module O = Ordered.Int

(* -------------------------------------------------------------------------- *)
(*  Persistent heaps                                                          *)
(* -------------------------------------------------------------------------- *)

module type PER_MAX =
sig
end

module type PER_MIN =
sig
end
